#!/usr/bin/env python

class TrieNode:
    def __init__(self):
        self.child = dict()
        self.is_end = False
    

class Trie:
    def __init__(self):
        self._root = TrieNode()
    
    def add(self, word):        
        cur = self._root
        for ch in word:
            if ch not in cur.child:
                cur.child[ch] = TrieNode()
            
            cur = cur.child[ch]
        
        cur.is_end = True
    
    def query(self, word):
        cur = self._root

        for ch in word:
            if cur is not None and ch in cur.child:
                cur = cur.child[ch]
            else:
                return False
        
        return cur.is_end
                
    def start_with(self, word):
        cur = self._root

        for ch in word:
            if ch in cur.child:
                cur = cur.child[ch]
            else:
                return False

        return True

    def __str__(self):
        def backtracking(node, word, alist):
            if node.is_end:
                alist.append("".join(word))
            
            for key, value in node.child.items():
                word.append(key)
                backtracking(value, word, alist)
                word.pop()
            
        ans = []
        backtracking(self._root, [], ans)

        return " ".join(ans)


if __name__ == "__main__":
    t = Trie()
    t.add('hello')
    t.add('here')
    t.add('hair')
    print(t.query('hair'))
    print(t.query('hare'))
    print(t.start_with('hell'))
    print(t.query('hell'))
    print(t.query('hello'))
    print(t)